/**
 * 两个已经排序好的数组，两个指针，一个计数器k
 * 两个数组从第一个元素开始遍历，每次将计数器加一，同时将较小的哪个数下标加一
 * 直到k等于两个数组长度的一一半，此时的哪个数就是中位数
 * 
 * 时间复杂度O(n)
 * 空间复杂度O(1)
 */

/**
 * 优化算法
 * 时间复杂度O(log2n) 
 * 空间复杂度O(1)
 * 
 * 分别求两个升序序列A，B的中位数为a，b求a,b的过程如下
 * 如果a=b，则a或b就是所求的中位数
 * 若a<b，则舍弃A中较小的一半，同时舍弃B中较大的一半，要求两次舍弃的长度相等
 * 若a>b，则舍弃A中较大的一半，同时舍弃B中较小的一半，要求两次舍弃的长度相等
 * 在保留的两个序列中，重复上面三行，直到两个序列中只有一个元素为止
 * 
 * 上面这个方法本质上是二分的思想
 */

/**
 * 所给的两个数组是等长的
 * 这里给出的中位数的定义和数学中的不一样
 * 这里是（长度/2向上取整）那个位置的元素是中位数，所以不用考虑奇偶
 * 
 */
#include<stdio.h>
int solution(int a[],int b[],int n){
    //s1,d1是a的起点和终点
    //s2,d2是b的...
    //m1 m2是a，b的中间下标
    int s1,d1,m1,s2,d2,m2;
    s1=0;d1=n-1;
    s2=1;d2=n-1;//为什么s2=1？
    while (s1!=d1||s2!=d2){
        m1=(s1+d1)/2;
        m2=(s2+d2)/2;
        if(a[m1]==b[m2])//二者相等，则就是所求的解
            return a[m1];
        if(a[m1]<b[m2]){//第一个的中位数小于第二个的中位数
            if((s1+d1)%2==0){//若元素个数为奇数，则舍弃A前半部分，B的后半部分，都保留中间点
                s1=m1;
                d2=m2;
            }else{//若元素个数为偶数，不保留中间点
                s1=m1+1;
                d2=m2;
            }
        }else{
            if((s1+d1)%2==0){
                d1=m1;
                s2=m2;
            }else{
                d1=m1;
                s2=m2+1;
            }
        }
    }
    return a[s1]<b[s2]?a[s1]:b[s2];
}

int main(void){
    int a[]={11,13,15,17,19};
    int b[]={2,4,6,8,20};
    int n=5;
    printf("%d\n",solution(a,b,n));
    return 0;
}